Bohater [B]
Limit pamięci: 128 MB
Na półkach bajtockich supermarketów pojawiła się właśnie nowa gra komputerowa,
w której kierujemy poczynaniami dzielnego herosa Bitora, mającego za zadanie pokonać
potworów zamieszkujących lochy Bajtogrodu.
Dla uproszczenia potwory będziemy numerować liczbami od
do
.
Podczas walki z potworem o numerze
Bitor doznaje obrażeń, które kosztują go
punktów życia.
Potwór ten broni skrzyni z eliksirem zdrowia, który po wygranej walce przywraca Bitorowi
punktów życia.
Bitor pokonuje potwory bez trudu, jednak nie może dopuścić, by w dowolnym momencie liczba jego punktów życia spadła do zera (lub poniżej).
Czy Bitor może stawać do walki z przeciwnikami w takiej kolejności, by pokonać wszystkie potwory?
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite
i
(
), oznaczające liczbę potworów i początkową liczbę punktów życia Bitora.
W kolejnych
wierszach znajdują się opisy potworów:
-ty z tych wierszy zawiera
dwie liczby całkowite
i
(
), oznaczające obrażenia zadawane przez potwora o numerze
oraz moc eliksiru, który można wypić po jego pokonaniu.
Wyjście
Pierwszy wiersz wyjścia powinien zawierać jedno słowo TAK lub NIE, w zależności od tego, czy Bitor jest w stanie pokonać wszystkie potwory.
Jeśli da się pokonać wszystkie potwory, należy wypisać także drugi wiersz zawierający ciąg
parami różnych liczb całkowitych z zakresu od
do
, pooddzielanych pojedynczymi odstępami.
Ciąg ten powinien opisywać przykładową kolejność toczenia walk, a jego
kolejne wyrazy powinny odpowiadać numerom kolejno pokonywanych potworów.
Jeśli istnieje więcej niż jedna poprawna odpowiedź, Twój program powinien wypisać dowolną z nich.
Przykład
Dla danych wejściowych:
3 5
3 1
4 8
8 3
poprawną odpowiedzią jest:
TAK
2 3 1
Autor zadania: Przemysław Uznański.